﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<iostream>
using namespace std;

enum Colour
{
	RED,
	BLANK
};

template<class K, class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED)
	{}
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;
};


template<class K, class V>
class RBTree
{
public:
	typedef RBTreeNode<K, V> Node;
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLANK;
			return true;
		}
		else
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first > kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_kv.first < kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}
			cur = new Node(kv);
			cur->_col = RED;
			if (parent->_kv.first > kv.first)
			{
				parent->_left = cur;
				cur->_parent = parent;
			}
			else
			{
				parent->_right = cur;
				cur->_parent = parent;
			}
			while (parent && parent->_col == RED)
			{
				Node* grandfather = parent->_parent;

				if (grandfather->_left == parent)
				{
					Node* uncle = grandfather->_right;
					if (uncle && uncle->_col == RED)
					{
						parent->_col = uncle->_col = BLANK;
						grandfather->_col = RED;
						cur = grandfather;
						parent = cur->_parent;
					}
					else
					{
						if (parent->_left == cur)
						{
							RatoteR(grandfather);
							parent->_col = BLANK;
							grandfather->_col = RED;
						}
						else
						{
							RatoteL(parent);
							RatoteR(grandfather);
							cur->_col = BLANK;
							grandfather->_col = RED;
							break;
						}
					}
				}
				else
				{
					Node* uncle = grandfather->_left;
					if (uncle && uncle->_col == RED)
					{
						parent->_col = uncle->_col = BLANK;
						grandfather->_col = RED;

						cur = grandfather;
						parent = cur->_parent;
					}
					else
					{
						if (parent->_right == cur)
						{
							RatoteL(grandfather);
							parent->_col = BLANK;
							grandfather->_col = RED;
						}
						else
						{
							RatoteR(parent);
							RatoteL(grandfather);
							cur->_col = BLANK;
							grandfather->_col = RED;
							break;
						}
					}
				}
			}
			_root->_col = BLANK;
		}
		return true;
	}

	void RatoteR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subR = subL->_right;

		parent->_left = subR;
		if (subR)
			subR->_parent = parent;

		Node* pparent = parent->_parent;
		subL->_right = parent;
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			subL->_parent = pparent;
			if (pparent->_left == parent)pparent->_left = subL;
			else pparent->_right = subL;
		}
		parent->_parent = subL;
	}

	void RatoteL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subL = subR->_left;

		parent->_right = subL;
		if (subL)
			subL->_parent = parent;

		Node* pparent = parent->_parent;
		subR->_left = parent;
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			subR->_parent = pparent;
			if (pparent->_left == parent)pparent->_left = subR;
			else
				pparent->_right = subR;
		}
		parent->_parent = subR;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)return;
		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}

	bool Check(Node* root, int ret, const int BlankNum)
	{
		if (root == nullptr)
		{
			if (ret != BlankNum)
			{
				cout << "存在黑色节点数量不相等的路径" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在连续的红色节点" << endl;
			return false;
		}
		if (root->_col == BLANK)
		{
			ret++;
		}
		return Check(root->_left, ret, BlankNum) && Check(root->_right, ret, BlankNum);
	}
	bool IsBalance()
	{
		if (_root == nullptr)return true;
		if (_root->_col == RED)return false;
		Node* cur = _root;
		int BlankNum = 0;
		while (cur)
		{
			if (cur->_col == BLANK)
				BlankNum++;
			cur = cur->_left;
		}
		int ret = 0;
		return Check(_root, ret, BlankNum);
	}
	int Height()
	{
		return _Height(_root);
	}

	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int LeftHeight = _Height(root->_left);
		int RightHeight = _Height(root->_right);
		return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
	}
	int Size()
	{
		return _Size(_root);
	}
	int _Size(Node* root)
	{
		if (root == nullptr)return 0;
		return _Size(root->_left) + _Size(root->_right) + 1;
	}
private:
	Node* _root = nullptr;
};